其他
363,数据结构-4,栈
基础知识
栈也是一种特殊的线性表,他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作,他就好像我们把书一本本的摞起来,最先放的书肯定是摞在下边,最后放的书肯定是摞在了最上面,摞的时候不允许从中间放进去,拿书的时候也是先从最上面开始拿,不允许从下边或中间抽出来。
栈的原理图
栈的实现可以使用数组也可以使用链表,我们这里分析的主要是使用数组的形式。
代码实现
栈的实现其实非常简单,常见的就两种操作,一种是压栈一种是出栈,我们来看下代码
1public class Stack<E> {
2 private Object[] data;
3 private int size;
4
5 public Stack(int capacity) {
6 if (capacity <= 0)
7 throw new IllegalArgumentException("栈的大小必须大于0");
8 data = new Object[capacity];
9 }
10
11 public void push(E item) {
12 if (isFull())
13 throw new IllegalArgumentException("栈已经满了");
14 data[size++] = item;
15 }
16
17 public E pop() {
18 if (isEmpty())
19 throw new IllegalArgumentException("栈是空的");
20 E temp = (E) data[--size];
21 data[size] = null;
22 return temp;
23 }
24
25 public E peek() {
26 if (isEmpty())
27 throw new IllegalArgumentException("栈是空的");
28 return (E) data[size - 1];
29 }
30
31 public boolean isEmpty() {
32 return size() == 0;
33 }
34
35 public boolean isFull() {
36 return size() == data.length;
37 }
38
39 public int size() {
40 return size;
41 }
42}
这里为了方便,栈的空间大小在初始化的时候就就已经固定了,并且栈满的时候没有扩容,栈是一个非常有用的数据结构,尤其在算法中用到的还是比较多的。栈是一种先进后出的数据结构,他和队列正好相反,队列是一种先进先出的数据结构。
例子
我们来看个非常简单的例子,验证括号的有效性,括号只包含"(",")","[","]","{","}"这6个字符,比如(),{()},[](){}都是有效的,而{],{(]}都是无效的。
我们来分析一下这道题,当我们遍历到括号的左半边的时候,我们把括号的右半边压栈,当我们遍历到括号右半边的时候,我们就把栈顶的元素弹出,然后在和我们遍历的符号比较看是否一样,我们以字符串"{([]())}"为例来画图分析一下,
搞懂了上面的图,写出代码就容易多了,我们来看下代码怎么实现
1public boolean isValid(String s) {
2 Stack<Character> stack = new Stack<>(s.length());
3 for (char c : s.toCharArray()) {
4 if (c == '(')
5 stack.push(')');
6 else if (c == '{')
7 stack.push('}');
8 else if (c == '[')
9 stack.push(']');
10 else if (stack.isEmpty() || stack.pop() != c)
11 return false;
12 }
13 return stack.isEmpty();
14}